#include <iostream>
#include <cstdlib>
#include <algorithm>

template<typename T>
class BinaryTree
{
private:
    class Node
    {
    public:
	T data;
	Node* lc;
	Node* rc;
	Node* parent;
	Node(T _data);
    };
    Node* root;
 public:
    void inorder_walk(Node* _x) const;
    void inorder_walk(Node* _x, T* _arr, int _l) const;
    void release(Node* _x);
    Node* successor(Node* _x) const;
    Node* predecessor(Node* _x) const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;
    Node* tree_search(T _data) const;
    BinaryTree() {root = NULL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    void inorder_walk() const;
    void inorder_sort_walk(T* _arr, int _l) const;
    void transplant(Node *_u, Node *_v);
    void del(Node *_x);
    void del(T _data);
    void test_search(T _data) const;
    void test_successor() const; 
    void test_predecessor() const;
    void test_min() const;
    void test_max() const;
    void test_del();
   
};
template <typename T> void BST_sort(T* arr, int _l);


template<typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    Node* p = new Node(_data);
    if (root == NULL)
	root = p;
};

template<typename T>
void BinaryTree<T>::release(Node* _x)
{
    if (_x != NULL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};

template<typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template<typename T>
BinaryTree<T>::Node::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->rc != NULL)
	return min(x->rc);
    Node* y = x->parent;
    while (y != NULL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template<typename T>
void BinaryTree<T>::test_successor() const
{
    std::cout << "successor: " << successor(root->lc->lc->rc)->data << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::predecessor(Node* _x) const
{
  Node* x = _x;
  if (x->lc != NULL)
    return max(x->lc);
  Node* y = x->parent;
  while (y != NULL && x == y->lc){
    x = y;
    y = y->parent;
  }
  return y;
}

template<typename T>
void BinaryTree<T>::test_predecessor() const
{
  std::cout << "predecessor: " << predecessor(root->rc->lc)->data << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::min(Node* _x) const
{
    while (_x->lc != NULL)
	_x = _x->lc;
    return _x;
};

template<typename T>
void BinaryTree<T>::test_min() const
{
  std::cout << "min: " << min(root->lc)->data << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::max(Node* _x) const
{
  while (_x->rc != NULL)
    _x = _x->rc;
  return _x;
}

template<typename T>
void BinaryTree<T>::test_max() const
{
  std::cout << "max: " << max(root)->data << std::endl;
};



template<typename T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != NULL)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << "  ";
	inorder_walk(_x->rc);
    }
};

template<typename T>
void BinaryTree<T>::inorder_walk(Node* _x, T* _arr, int _l) const
{
  static int k=0;
  if (_x != NULL)
    {
      inorder_walk(_x->lc,_arr,_l);
      if (k < _l){
	_arr[k]=_x->data;
	k++;
      }
      inorder_walk(_x->rc,_arr,_l);
    }
};

template<typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template<typename T>
void BinaryTree<T>::inorder_sort_walk(T* _arr, int _l) const
{
  inorder_walk(root,_arr,_l);
};

template<typename T>
void BinaryTree<T>::insert(T _data)
{
    Node* y = NULL;
    Node* x = root;
    Node* p = new Node(_data);
    while (x != NULL)
    {
	y = x;
	if (p->data  < x->data)
	    x = x->lc;
	else
	    x = x->rc;
    }
    p->parent = y;
    if (y == NULL)
	root = p;
    else if (p->data < y->data)
	y->lc = p;
    else
	y->rc = p;
};


template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::tree_search(T _data) const
{
  Node* x = root;
  while (x != NULL){
    if (x->data > _data)
      x = x->lc;
    else if (x->data < _data)
      x = x->rc;
    else
      return x;
  }
  return NULL;
}


template<typename T>
void BinaryTree<T>::test_search(T _data) const
{
  Node* p = tree_search(_data);
  if (p == NULL)
    std::cout << "Not Found" << std::endl;
  else{
    if (p->parent == NULL)
      std::cout << "root!" << std::endl;
    else
      std::cout << "parent:" << p->parent->data << std::endl;
    if (p->lc != NULL)
      std::cout << "left child:" << p->lc->data << std::endl;
    if (p->rc != NULL)
      std::cout << "right child:" << p->rc->data << std::endl;
  }
};

template <typename T> void BST_sort(T* _arr, int _l){
  BinaryTree<T> A;
  std::random_shuffle(_arr,_arr+_l);
  for (int i=0; i<_l ; i++)
    A.insert(_arr[i]);
  A.inorder_sort_walk(_arr,_l);
}

template<typename T>
void BinaryTree<T>::transplant(Node *_u, Node *_v){
  if (_u == NULL){
    std::cerr << "Error! Can not transplant to a NULL."
                  << std::endl;
    std::exit(-1);
  }
  if (_u->parent == NULL)
    root = _v;  
  else if (_u == _u->parent->lc)
    _u->parent->lc = _v;
  else
    _u->parent->rc = _v;
  _v->parent = _u->parent;
}

template<typename T>
void BinaryTree<T>::del(Node *_x){
  if (_x != NULL){
    if (_x->lc == NULL)
      this->transplant(_x, _x->rc);
    else if (_x->rc == NULL)
      this->transplant(_x, _x->lc);
    else{
      Node *y = min(_x->rc);
      if (y->parent != _x){
	this->transplant(y, y->rc);
	y->rc = _x->rc;
	y->rc->parent = y;
      }
      this->transplant(_x, y);
      y->lc = _x->lc;
      y->lc->parent = y;
    }
    delete _x;
  }
}


template<typename T>
void BinaryTree<T>::del(T _data){
  Node* y = this->tree_search(_data);
  this->del(y);  
}


template<typename T>
void BinaryTree<T>::test_del(){
  this->del(root->rc);
}
